1. Technical Field
Generally, the present invention relates to compressing digital data. Specifically, the present invention relates to compressing digital data in real-time environments by using tree structures to compress and decompress the data.
2. Description of the Related Art
The ability to communicate digital information from one point to another is an important part of the modem world. Due to this importance, digital communication products are continually improved, allowing for more data to be communicated between two points at ever increasing speeds. However, every type of digital communication system has inherent limitations on the amount of data which can be transmitted. In light of these limitations, the need to efficiently transmit digital data over a given medium is always present.
One common manner to increase the efficiency of a digital communication is to compress the data before it is sent, then decompress the data upon reception. In this way, the same information is sent using less data to represent the information. Some compression methods compress data in such a manner that a portion of the information originally contained in the data is lost. When this data is received and decompressed, the data only represents an approximation of the original information. These type of compression methods allow for very large compression ratios to be achieved, and are commonly used when transmitting audio and visual information (e.g., voice conversations, music, and television signals) which is meant to be consumed by the human senses. Studies have shown that the human senses of sight and hearing often cannot detect the absence of the information removed by the compression routines, thus, the quality of the information is not perceptively affected and the information is transmitted more efficiently.
For other types of digital communications, the loss of even a single piece of information can render the entire transmission unusable. This is often the case when one data processing system is communicating with another. In these instances, the compression routines must compress the data to be transmitted in such a manner that all of the information contained in the original message is present in the compressed form of the message.
Such compression/decompression routines are often measured in terms of their compression efficiency, and the rate at which they can compress the data. Many routines strive to optimally compress a given set of data, but suffer from the fact that they must extensively process the data during this compression, and hence execute slowly. Other compression/decompression routines cannot efficiently compress a set of data, but these routines often compress the data very quickly. Both types of compression/decompression routines find use in the many types of digital communication systems now available.
However, it would be desirable to create a set of compression/decompression routines which achieves a high compression efficiency, while not requiring the data to be processed extensively. Such routines would find use in the many digital communication systems that benefit from transmitting highly compressed data, but cannot afford to spend a great amount of time compressing and decompressing the data. One example of a digital communication system which would benefit from such compression/decompression routines is a typical local area network. The data processing systems typically connected to a local area network often do not have the processing power to extensively compress and decompress data in a timely manner. However, those local area networks would benefit greatly from having to communicate smaller amounts of data.